package class10;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode.cn/problems/FortPu/description/
 *
 * 插入和删除随机元素O(1)时间的结构
 * 解题思路：
 * 1.用hashmap存储，value 和 index，
 * 2.使用数组arr,存储value
 * 3.当插入数据时，实际上是arr数组存具体值
 * 4.注意删除是否为最后一个元素问题
 */
public class Code11_InsertDeleteRandom {
    public static void main(String[] args) {
        RandomizedSet set = new RandomizedSet();
        System.out.println(set.delete(0));
        System.out.println(set.delete(0));
        System.out.println(set.insert(0));
        System.out.println(set.getRandom());
        System.out.println(set.delete(0));
        System.out.println(set.insert(0));
        System.out.println("set = " + set);

    }

    private static class RandomizedSet {
        public Map<Integer, Integer> map;
        public int[] arr;
        public int r;
        public final int MAX = 2*100000;

        public RandomizedSet() {
            map = new HashMap<>();
            arr = new int[MAX];
            r=0;
        }

        public boolean insert(int v) {
            if (map.containsKey(v)) {
                return false;
            }
            arr[r] = v;
            map.put(v, r++);
            return true;
        }

        public boolean delete(int v) {
            if (!map.containsKey(v)) {
                return false;
            }
            Integer index = map.remove(v);
            if (index < r - 1) { // 如果删除的不是最后一个元素，则进行交换
                arr[index] = arr[r - 1];
                map.put(arr[index], index);
            }
            r--;
            return true;
        }

        public int getRandom() {
            return arr[(int) (Math.random() * r)];
        }
    }
}
